package q207_canFinish;

import java.util.ArrayList;
import java.util.List;

public class Solution_2 {

    List<List<Integer>> edges;
    int[] visited;
    boolean valid = true;

    /**
     * 利用DFS的方法来解决该问题 实际上和BFS有一定的类似
     * 前几步都是构建邻接表等
     * 然后对度为0的进行相应的操作
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
            edges = new ArrayList<>();
            for (int i = 0; i < numCourses; ++i) {
                edges.add(new ArrayList<>());
            }
            visited = new int[numCourses];
            for (int[] info : prerequisites) {
                edges.get(info[1]).add(info[0]);
            }
            for (int i = 0; i < numCourses && valid; ++i) {
                if (visited[i] == 0) {
                    dfs(i);
                }
            }
            return valid;
        }

        public void dfs ( int u){
            visited[u] = 1;
            for (int v : edges.get(u)) {
                if (visited[v] == 0) {
                    dfs(v);
                    if (!valid) {
                        return;
                    }
                } else if (visited[v] == 1) {
                    valid = false;
                    return;
                }
            }
            visited[u] = 2;
        }


}
